package 单周赛.history;

import java.util.*;

/**
 *
 */
public class 第355场单周赛 {

    public static void main(String[] args) {


    }

    /**
     * 双指针
     */
    public List<String> splitWordsBySeparator(List<String> words, char separator) {
        List<String> list = new ArrayList<>();

        for (String word : words) {
            int left = 0, right = 0;

            while (right < word.length()) {
                while (right < word.length() && word.charAt(right) != separator) {
                    right++;
                }
                String s = word.substring(left, right);
                if (s.length() > 0) {
                    list.add(s);
                }

                left = right + 1;
                right = left;
            }
        }
        return list;
    }

    /**
     * 贪心思想
     * 从后往前遍历，后面的值越大，越有可能将前面的值吞并
     */
    public long maxArrayValue(int[] nums) {
        long ans = nums[0];
        Deque<Long> stack = new ArrayDeque<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            if (!stack.isEmpty() && nums[i] <= stack.peekFirst()) {
                Long peek = stack.pollFirst();
                stack.addFirst(nums[i] + peek);
            } else {
                stack.addFirst(Long.valueOf(nums[i]));
            }
        }

        while (!stack.isEmpty()) {
            ans = Math.max(ans, stack.pollFirst());
        }
        return ans;
    }

    /**
     * 优先队列+模拟（超时）
     * 从长度为 1 的数组开始模拟，优先从队列中取数量最多的数字，同一次选择
     * 中不能从队列中选同一个数字
     */
    public int maxIncreasingGroups(List<Integer> usageLimits) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> b - a);
        for (int i = 0; i < usageLimits.size(); i++) {
            priorityQueue.add(usageLimits.get(i));
        }

        int ans = 1;
        while (true) {
            List<Integer> cache = new ArrayList<>();
            if (priorityQueue.size() < ans) {
                return ans - 1;
            }
            for (int i = 0; i < ans; i++) {
                int poll = priorityQueue.poll();
                if (poll <= 0) {
                    return ans - 1;
                }
                if (poll > 1) {
                    cache.add(poll - 1);
                }
            }

            priorityQueue.addAll(cache);
            ans++;
        }
    }

}
